package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/3.
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class TestProblem36 {

    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode lastNode = null;
        TreeNode headNode = ConvertNode(pRootOfTree, lastNode);
        //找到转换后的链表的头节点
        while (headNode != null && headNode.left != null)
            headNode = headNode.left;
        return headNode;
    }

    public static TreeNode ConvertNode (TreeNode rootNoed, TreeNode lastNode) {

        if (rootNoed == null) return null;

        //递归左子树
        if (rootNoed.left != null)
            ConvertNode(rootNoed.left,lastNode);
        //当前节点的左指针指向最后一个节点
        rootNoed.left = lastNode;

        if (lastNode != null)
            //最后一个节点的右指针指向当前节点
            lastNode.right = rootNoed;
        //更新已经转换好的链表的最后一个节点
        lastNode = rootNoed;

        if (rootNoed.right != null)
            lastNode = ConvertNode(rootNoed.right,lastNode);

        return lastNode;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(10);
        TreeNode b = new TreeNode(6);
        TreeNode c = new TreeNode(14);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(8);
        TreeNode f = new TreeNode(12);
        TreeNode g = new TreeNode(16);
        a.left = b;a.right = c;c.left = d;c.right = e;c.left = g;c.left = f;
        TreeNode convert = Convert(a);
        System.out.println(convert);

    }

}
